/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */

#ifndef ALBERO_H_
#define ALBERO_H_

#include <iostream>
using namespace std;

#define NDEBUG
#include <cassert>

#include "nodoAn.h"

template <class T>
class Albero {

public:

	typedef typename NodoAn<T>::posizione posizione;

	Albero();
	Albero(int);
	~Albero();

	void creaAlbero();
	bool alberoVuoto();
	posizione radice()  throw (char const *) ;
	posizione padre( posizione )  throw (char const *) ;
	posizione primoFiglio( posizione )  throw (char const *) ;
	posizione fratelloDestro( posizione )  throw (char const *) ;
	bool ultimoFratello( posizione ) throw (char const *) ;
	bool foglia( posizione ) throw (char const *) ;

	void insRadice() throw (char const *);
	void insRadice( T ) throw (char const *);

	void insPrimoFiglio( posizione ) throw (char const *);
	void insPrimoFiglio( posizione, T ) throw (char const *);

	void insFratelloDestro( posizione ) throw (char const *);
	void insFratelloDestro( posizione, T ) throw (char const *);

	void cancSottoAlbero( posizione ) throw (char const *);

	T leggiNodo( posizione ) throw (char const *);
	void scriviNodo( posizione, T ) throw (char const *);

	//operatori personalizzati
	void print();
	void print( posizione );

private:
	int maxLung;
	int nNodi;
	NodoAn<T> * tree;
	posizione root;
	posizione libera;
};




//DEFINIZIONE

template <class T>
Albero<T>::Albero() {
	maxLung = 50;
	tree = new NodoAn<T>[ maxLung ];
	creaAlbero();
}

template <class T>
Albero<T>::Albero(int n) {
	maxLung = n;
	tree = new NodoAn<T>[ maxLung ];
	creaAlbero();
}

template <class T>
Albero<T>::~Albero() {
	if ( !alberoVuoto() )
		cancSottoAlbero( root );
}


template <class T>
void Albero<T>::creaAlbero() {
	root = -1;
	nNodi = 0;
	libera = 0;
	for (int i=0; i<maxLung; i++) {
		tree[i].setPrimoFiglio(i+1);
	}
}



template <class T>
bool Albero<T>::alberoVuoto() {
	return ( nNodi == 0 );
}



template <class T>
typename Albero<T>::posizione Albero<T>::radice() throw (char const *) {
	if ( !alberoVuoto() )
		return root;
	else
		throw "Albero Vuoto.";
}


template <class T>
typename Albero<T>::posizione Albero<T>::padre( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( p != radice() )
				return tree[p].getPadre();
			else
				throw "La radice non ha padre.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
typename Albero<T>::posizione Albero<T>::primoFiglio( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( tree[p].getPrimoFiglio() != -1 )
				return tree[p].getPrimoFiglio();
			else
				throw "Il nodo non ha figli.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
typename Albero<T>::posizione Albero<T>::fratelloDestro( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( tree[p].getFratelloDestro() != -1 )
				return tree[p].getFratelloDestro();
			else
				throw "Il nodo non ha fratello destro.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}



template <class T>
bool Albero<T>::ultimoFratello( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( tree[p].getFratelloDestro() == -1 )
				return true;
			else
				return false;
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}




template <class T>
bool Albero<T>::foglia( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( tree[p].getPrimoFiglio() == -1 )
				return true;
			else
				return false;
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::insRadice() throw (char const *) {
	if ( alberoVuoto() ) {
		creaAlbero();
		root = libera;
		libera = tree[libera].getPrimoFiglio();

		tree[root].setPadre( -1 );
		tree[root].setPrimoFiglio( -1 );
		tree[root].setFratelloDestro( -1 );
		tree[root].setPresente( true );

		nNodi++;
	} else
		throw "Albero non vuoto.";
}

template <class T>
void Albero<T>::insRadice( T elem ) throw (char const *) {
	insRadice();
	scriviNodo( root, elem );
}


template <class T>
void Albero<T>::insPrimoFiglio( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( ! alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( foglia(p) ) {

				posizione temp = libera;
				libera = tree[libera].getPrimoFiglio();

				tree[temp].setPadre(p);
				tree[temp].setPrimoFiglio( -1 );
				tree[temp].setFratelloDestro( -1 );
				tree[temp].setPresente(true);

				tree[p].setPrimoFiglio( temp );
				nNodi++;

			}
			else
				throw "Il nodo ha già un figlio.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::insPrimoFiglio( posizione p, T elem ) throw (char const *) {
	insPrimoFiglio( p );
	scriviNodo( tree[p].getPrimoFiglio(), elem );
}


template <class T>
void Albero<T>::insFratelloDestro( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( ! alberoVuoto() )
		if ( tree[p].isPresente() )
			if ( tree[p].getFratelloDestro() == -1 ) {
				posizione temp = libera;
				libera = tree[libera].getPrimoFiglio();

				tree[temp].setPadre( tree[p].getPadre() );
				tree[temp].setPrimoFiglio( -1 );
				tree[temp].setFratelloDestro( -1 );
				tree[temp].setPresente(true);

				tree[p].setFratelloDestro( temp );
				nNodi++;
			}
			else
				throw "Il nodo ha già un fratello destro.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::insFratelloDestro( posizione p, T elem ) throw (char const *) {
	insFratelloDestro( p );
	scriviNodo( tree[p].getFratelloDestro(), elem );
}




template <class T>
void Albero<T>::cancSottoAlbero( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( ! alberoVuoto() )
		if ( tree[p].isPresente() ) {
			while ( !foglia(p) )
				cancSottoAlbero( tree[p].getPrimoFiglio() );

			if ( tree[p].getPadre() != -1)
				tree[ tree[p].getPadre() ].setPrimoFiglio( tree[p].getFratelloDestro() );
			else
				root = tree[p].getFratelloDestro();

			tree[p].setPresente( false );
			tree[p].setPadre( -1 );
			tree[p].setPrimoFiglio( libera );
			tree[p].setFratelloDestro( -1 );
			libera = p;
			nNodi--;
		}
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}



template <class T>
T Albero<T>::leggiNodo( posizione p ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			return tree[p].getValue();
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::scriviNodo( posizione p, T elem ) throw (char const *) {
	assert(p!=-1);
	if ( !alberoVuoto() )
		if ( tree[p].isPresente() )
			tree[p].setValue(elem);
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}



template <class T>
void Albero<T>::print() {
	if ( alberoVuoto() )
		cout << "[Empty]" << endl;
	else
		print( root );
}


template <class T>
void Albero<T>::print( posizione p ) {
	assert(p!=-1);

	cout << leggiNodo(p);
	if ( foglia(p) )
		return;
	cout << " (";
	posizione q = tree[p].getPrimoFiglio() ;
	while ( q != -1 ) {
		cout << " ";
		print(q);
		cout << " ";
		q = tree[q].getFratelloDestro() ;
	}
	cout << ")";
}


#endif /* MAIN_CPP_ */
